package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-07 15:34
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 戳气球 {

    int[] nums1;
    int[][] f;

    // 决策：最后一个戳p
    public int maxCoins(int[] nums) {
        int n = nums.length;
        nums1 = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            nums1[i] = nums[i - 1];
        }
        nums1[0] = 1;
        nums1[n + 1] = 1;
        // 戳破 i - j 能够获得的钱
        f = new int[n + 1][n + 1];
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= n ; j++) {
                f[i][j] = -1;
            }
        }
        return calc(1,n);
    }

    private int calc(int l, int r) {
        if (l > r) return 0;
        if (f[l][r]!=-1) return f[l][r];
        for (int p=l;p<=r;p++){
            f[l][r] = Math.max(f[l][r],calc(l,p-1)+calc(p+1,r) + nums1[p] * nums1[l-1] * nums1[r+1]);
        }
        return f[l][r];
    }

}
